package jiejie.jianzhioffer;

import java.util.Arrays;
import java.util.Stack;

public class offer06 {
    public static void main(String[] args) {
        ListNode node1=new ListNode(1);
        ListNode node2=new ListNode(2);
        ListNode node3=new ListNode(3);
        ListNode node4=new ListNode(4);
        ListNode node5=new ListNode(5);
        node1.next=node2;
        node2.next=node3;
        node3.next=node4;
        node4.next=node5;
        node5.next=null;
        int[] ans=reversePrint1(node1);
        String s=Arrays.toString(ans);
        System.out.println(s);


    }
    /**
     * 从尾到头打印链表
     * @param head
     * @return
     */
    public static int[] reversePrint(ListNode head) {
        int[] res= new int[getLen(head)];
        ListNode nNode=reverseList(head);
        int start=0;
        while(nNode!=null){
            res[start]=nNode.val;
            nNode=nNode.next;
            start++;
        }
        return res;
    }
    public static int getLen(ListNode head){
        int ans=0;
        while(head!=null){
            ans++;
            head=head.next;
        }
        return ans;
    }
    public static ListNode reverseList(ListNode head){
        if(head==null||head.next==null)
            return head;
        ListNode pNode=null;
        ListNode cNode=head;

        while(cNode!=null){
            ListNode nNode=cNode.next;
            cNode.next=pNode;
            pNode=cNode;
            cNode=nNode;
        }
        return pNode;
    }

    /**
     * 方法二，借助栈，先入后出
     * @param head
     * @return
     */
    public static int[] reversePrint1(ListNode head){
        Stack<ListNode> stack = new Stack<>();
        ListNode node=head;
        while(node!=null){
            stack.push(node);
            node=node.next;
        }
        int [] res=new int[stack.size()];
        int size=stack.size();
        for(int i=0; i<size; i++){
            res[i]=stack.pop().val;
        }
        return res;
    }

}